package com.zhugang.week13.linkedlist;

import org.junit.Test;

import java.util.HashSet;
import java.util.function.Predicate;

import static org.junit.Assert.assertEquals;

/**
 * @program algorithms
 * @description: list
 * @author: chanzhugang
 * @create: 2022/10/08 14:15
 */
public class List<T> {

    // 头节点
    Node<T> head = null;

    class Node<T> {
        Node<T> next = null;
        T data;

        public Node(T data) {
            this.data = data;
        }
    }

    /**
     * 头插法
     *
     * @param data
     */
    public void insert(T data) {
        Node<T> node = new Node<>(data);
        node.next = head;
        head = node;
    }

    /**
     * 查找元素
     *
     * @param predicate
     * @return
     */
    public Node<T> find(Predicate<T> predicate) {
        Node<T> p = head;
        while (p != null) {
            if (predicate.test(p.data)) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    /**
     * 链表大小
     *
     * @return
     */
    public int size() {
        Node<T> p = head;
        int count = 0;
        while (p != null) {
            count++;
            p = p.next;
        }
        return count;
    }

    /**
     * 删除指定节点
     *
     * @param node
     */
    public void remove(Node<T> node) {
        // prev.next = prev.next.next
        if (head == null) {
            // 链表为null
            return;
        }
        if (head == node) {
            // 头节点是要删除的节点
            head = head.next;
            return;
        }
        // 快慢指针
        var slow = head;
        var fast = head.next;
        while (fast != node && fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        if (fast != null) {
            // 此时 fast == node，是要删除的节点, slow是fast的前置节点
            slow.next = fast.next;
        }
    }


    /**
     * 206、反转链表
     * https://leetcode.cn/problems/reverse-linked-list/
     */
    public void reverse1() {
        // 三指针法：每次反转一个指针，其他指针往后挪一位
        Node<T> prev = null;
        Node<T> current = head;
        Node<T> next;
        while (current != null) {
            // 临时存储下一个节点
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }

    public Node<T> reverse2(Node<T> head) {
        // 1-2-3-4-5  -> 5-4-3-2-1
        // 递归写法
        if (head == null || head.next == null) {
            // 终止条件：链表为null 或者只有一个节点
            return head;
        }
        Node<T> rest = reverse2(head.next);
        head.next.next = head;
        head.next = null;
        return rest;
    }

    /**
     * 141、环形链表
     * https://leetcode.cn/problems/linked-list-cycle/
     *
     * @return
     */
    public boolean hasLoop1() {
        // Set + 遍历
        var p = head;
        var set = new HashSet<>();
        while (p != null) {
            if (set.contains(p)) {
                return true;
            }
            set.add(p);
            p = p.next;
        }
        return false;
    }

    public boolean hasLoop2() {
        // 快慢指针：快指针每次走两步
        if (head == null || head.next == null) {
            // 链表为null 或者 只有一个节点
            return false;
        }
        var slow = head;
        var fast = head.next.next;
        while (fast != null && fast.next != null) {
            if (fast == slow) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

    @Test
    public void test_insert() {
        var list = new List<Integer>();
        list.insert(1);
        list.insert(2);
        list.insert(3);

        var p = list.head;
        for (Integer i = 3; p != null; i--) {
            assertEquals(i, p.data);
            p = p.next;
        }
    }

    @Test
    public void test_find_remove() {
        var list = new List<String>();
        list.insert("C++");
        list.insert("Java");
        list.insert("C");
        list.insert("C#");
        list.insert("python");

        var node = list.find(x -> x == "Java");
        assertEquals("Java", node.data);

        var node2 = list.find(x -> x == "ruby");
        assertEquals(null, node2);

        list.remove(node);
        //assertEquals(Integer.valueOf(4), list.size());
        assertEquals(null, list.find(x -> x == "Java"));
    }

    @Test
    public void test_reverse() {
        var list = new List<Integer>();

        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.reverse1();

        var p = list.head;
        for (Integer i = 1; p != null; i++) {
            assertEquals(i, p.data);
            p = p.next;
        }
    }

    @Test
    public void test_loop() {
        var list = new List<Integer>();
        list.insert(3);
        list.insert(2);
        list.insert(1);
        list.insert(0);
        var node = list.find(x -> x == 3);
        // 设置环
        node.next = list.head;

        assertEquals(true, list.hasLoop1());
        assertEquals(true, list.hasLoop2());

    }


}